// https://leetcode.cn/problems/trapping-rain-water/?envType=study-plan-v2&envId=top-100-liked

// 算法思路总结：
// 1. 按层计算雨水容量，从低到高逐层处理
// 2. 双指针从两端向中间扫描每层可接雨水区域
// 3. 减去已有柱子高度得到实际雨水容量
// 4. 累计所有层数的雨水总量
// 5. 时间复杂度：O(max(height))，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    int trap(vector<int>& height) 
    {
        int m = height.size();

        int l = 0, r = m - 1;
        int ret = 0, curheight = 0;

        while (l <= r)
        {
            while (l <= r && height[l] <= curheight)
            {
                ret -= height[l++];
            }
            while (l <= r && height[r] <= curheight)
            {
                ret -= height[r--];
            }
            ret += r - l + 1;
            curheight++;
        }

        return ret;
    }
};

int main()
{
    vector<int> nums1 = {0,1,0,2,1,0,1,3,2,1,2,1};
    vector<int> nums2 = {4,2,0,3,2,5};

    Solution sol;

    cout << sol.trap(nums1) << endl;
    cout << sol.trap(nums2) << endl;

    return 0;
}